\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}

\pagestyle{headings}

\title{Graph设计思路和测试说明}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{项目设计思路}
为了实现Bellman-Ford算法，我先在顶点类中增加了私有属性distance，用来存储每个顶点到源点的最短距离。函数以图中某个顶点的值作为输入，若输入顶点不存在则报错中止函数。函数体则根据Bellman-Ford算法的核心思路，通过n-1次对所有的边进行松弛操作解决单源最短路径问题，其中n为图中的顶点数。同时通过第n次遍历所有的边检查图中是否有负值环，若仍能松弛则图中有负值环，此时报错并中止函数。另外我还增加了函数superBellmanFord()，是队列优化过的bellmanford算法，通过队列防止最大次数n-1的松弛所有边的操作，当然其最坏情况效率仍为O(VE)。
\section{测试说明}
在main函数中调用了3个测试函数，分别测试了邻接表有向图、邻接矩阵有向图的BellmanFord函数、函数的异常处理,及验证了BellmanFord函数的效率和顶点数n的线性关系。经测试函数设计没有问题，能正确给出到源点的最短路径。根据理论分析Bellman做了n次对边的遍历，因此其效率为O(VE)。测试函数中我固定边的数量为90，通过改变顶点的数量来验证BellmanFord函数的效率和顶点数n的线性关系。测试数据如图，约为线性关系，理论正确。另外，队列优化的bellmanford速度快于原算法。经测试无内存泄漏。
\begin{figure}[htbp]
  \centering
  \begin{minipage}{12cm}
    \centering
    \includegraphics[width=12cm,height=6cm]  {pic/验证效率.png}
  \caption{验证算法效率与顶点数成线性关系}
  \end{minipage}
\end{figure}
\end{document}
